ECE 6605 - Information Theory

Prof. Matthieu Bloch

Thursday September 21, 2023

Announcements

  • Assignment 2
    • Posted on Canvas/Gradescope on Monday, September 18, 2023
    • Due on Thursday September 28, 2023
    • 6 problems on chain rules, typicality
    • Read Chapter 4 of Thomas M. Cover and Joy A. Thomas, Elements of Information Theory
  • Last time
    • Converse for source coding
    • Random binning for achievability proof
    • One-shot result, smoothing
  • Today
    • Applications of one-show result
    • Smoothing
    • Large \(n\) regime
    • A cool new result: Source coding with side information

Fixed-length source coding

Image
Fixed-length source coding model

A fixed-lenght \((n,M_n)\) code for a discrete memoryless source \(p_X\) consists of:

  1. A encoding function \(f_n:\calX^n\to\set{1;M_n}\)
  2. A decoding function \(g_n:\set{1;M_n}\to \calX^n\)
  • The performance of an \((n,M_n)\) code is measured in terms of
    1. The rate of the code \(R\eqdef \frac{\log_2 M_n}{n}\) (bits/source symbol)

    2. The average probability of error

      \[\begin{align*} P_e^{(n)}(\calC) \eqdef \P{\widehat{X}^n\neq X^n} \eqdef \sum_{x^n\in\calX^n}P_X^{\otimes n}(x^n)\indic{g_n(f_n(x^n))\neq x^n}. \end{align*}\]

Source coding theorem

Consider a sequence of fixed length \((n,M_n)\) source codes \(\set{(f_n,g_n)}_{n\geq1}\) such that \[ \lim_{n\to\infty}\frac{\log M_n}{n}\leq R \text{ and } \lim_{n\to\infty}P_e^{(n)}=0 \] Then \(R\geq \bbH(X)\) so that \(C_{\textsf{source}}\geq \bbH(X)\).

For any \(R>\bbH(X)\), there exists a sequence of fixed length \((n,M_n)\) source codes \(\set{(f_n,g_n)}_{n\geq1}\) such that \[ \lim_{n\to\infty}\frac{\log M_n}{n}\leq R \text{ and } \lim_{n\to\infty}P_e^{(n)}=0 \] Hence, \(C_{\textsf{source}}\leq \bbH(X)\).

For a discrete memoryless source \(p_X\), \(C_{\textsf{source}} = \bbH(X)\)

Achievability - One Shot Lemma

  • The achievability follows using a technique called random binning
  • Consider a source \(P_U\) assume \(\textsf{supp}(U) = \calU\), and set \(n=1\) for simplicity
  • Define the set \[ \calB_\gamma\eqdef\left\{u\in\calU:\log\frac{1}{P_{U}(u)}\leq\gamma\right\}. \]
    • Encoding function \(f:\calU\to \set{1;M}\) created by assigning an index uniformly at random in \(\set{1;M}\) to each \(u\in\calU\)
    • Decoding function \(g:\intseq{1}{M}\to\calU :m\mapsto u^*\), where \(u^*\) is the unique sequence such that \(u^*\in\calB_\gamma\) and \(f(u^*)=m\); if \(u^*\) does not exist, a random \(u\) is declared

On average (over the random binning to create \(F\)), \[ \E[C]{P_e} \leq \P[P_{U}]{U\notin \calB_\gamma} + \frac{2^{\min(\gamma,\log_2\abs{\calU})}}{M}. \]

Achievability - Specializing one shot lemma

  • Approach 1: worst case analysis for \(\E{P_e}\leq \epsilon\)

    • Choose \(\gamma \eqdef -\log_2\min_{u\in{\calU}}p_U(u)\)

    \[ \log M = \log_2\card{\calU} + \log_2\frac{1}{\epsilon} \eqdef H_0(U) + \log_2\frac{1}{\epsilon} \]

  • Approach 2: smoothing

    • Note that \[ \P{\widehat{U}\neq U} \leq \bbV(P_U,\tilde{P}_U) + \sum_{u}\tilde{P}(u)\P{\widehat{U}\neq U|U=u} \]
    • Pick the best \(\tilde{P}_U\) close to \(P_U\)
    • Fix \(\epsilon_1,\epsilon_2>0\) such that \(\epsilon=\epsilon_1+\epsilon_2\) \[ \log M = \min_{\widetilde{P}_U\in\calB^{\epsilon_1}(P_U)} \log_2\textsf{supp}(\widetilde{P}_{U}) +\log_2\frac{1}{\epsilon_2} \eqdef H_0^{\epsilon_1}(U) + \log_2\frac{1}{\epsilon_2} \]
  • This offers partial answers to Question 1 if we substitute \(P_U\longleftarrow P_X^{\otimes n}\)

Achievability - Specializing one shot lemma

  • Approach 3: take the limit of \(n\) i.i.d. repetitions directly
    • \(P_U\longleftarrow P_X^{\otimes n}\)
    • \(\gamma = n(\H{X}+\epsilon)\) for some \(\epsilon>0\) so that
    \[ \lim_{n\to\infty} P_e^{(n)} = 0 \qquad\textsf{(exponentially fast in $n$)} \]

There exists a sequence of fixed length \((n,M_n)\) source codes \(\set{(f_n,g_n)}_{n\geq1}\) such that \[ \lim_{n\to\infty}\frac{\log M_n}{n}\leq \H{X} \text{ and } \lim_{n\to\infty}P_e^{(n)}=0 \]

  • Could we use Approach 2 directly? Yes \[ H_0^{\epsilon}(P_X^{\otimes n}) \geq n\H{X} + n\delta \qquad \text{ with } \epsilon = 2^{-\frac{n\delta^2}{2\log^2(\card{\calX}+3)}}. \]

Achievability - Specializing one shot lemma

  • Approach 4: take a refined view of the limit of \(n\) i.i.d. repetitions

Let \(\set{X_i}\) by i.i.d. random variables such that \(\E{X_i}=0\), \(\E{X_i^2}=\sigma^2<\infty\) and \(\E{\abs{X_i}^3}=\rho<\infty\). Define \[ Y_n = \frac{1}{n}\sum_{i=1}^nX_i \] and \(F_n\) the distribution of \(\frac{Y_n\sqrt{n}}{\sigma}\). There exists \(C\geq 0\) such that \[ \forall x\quad\forall n\quad\abs{F_n(x)-\Phi(x)}\leq \frac{C\rho}{\sigma^2\sqrt{n}} \] and \(\Phi\) is the CDF of the standard normal distribution.

Source coding with side information

Image
Fixed-length source coding with side information model

A \((n,M_n)\) code for source coding a discrete memoryless source \(p_X\) with side information \(Y\) consists of:

  1. A encoding function \(f_n:\calX^n\to\set{1;M_n}\)
  2. A decoding function \(g_n:\set{1;M_n}\times\calY^n\to \calX^n\)
  • The performance of an \((n,M_n)\) code is measured in terms of
    1. The rate of the code \(R\eqdef \frac{\log_2 M_n}{n}\) (bits/source symbol)

    2. The average probability of error

      \[\begin{align*} P_e^{(n)}(\calC) \eqdef \P{\widehat{X}^n\neq X^n} \eqdef \sum_{(x^n,y^n)\in\calX^n\times\calY^n}P_{XY}^{\otimes n}(x^n,y^n)\indic{g_n(f_n(x^n),y^n)\neq x^n}. \end{align*}\]

Source coding with side information

  • Define again \[ C_{\textsf{source}}\eqdef \inf\left\{R: \exists {(f_n,g_n)}_{n\geq 1} \textsf{ with }\lim_{n\to\infty}\frac{\log M_n}{n}\leq R \text{ and } \lim_{n\to\infty}P_e^{(n)}=0\right\} \]

For a discrete memoryless source \(P_{XY}\), \(C_{\textsf{source}} = \bbH(X|Y)\)

  • This should be suprising: the decoder does not know \(y^n\)

Consider a sequence of \((n,M_n)\) codes \(\set{(f_n,g_n)}_{n\geq1}\) such that \[ \lim_{n\to\infty}\frac{\log M_n}{n}\leq R \text{ and } \lim_{n\to\infty}P_e^{(n)}=0 \] Then \(R\geq \bbH(X|Y)\).

Achievability - One Shot Lemma

  • The achievability uses again random binning

  • Consider a source \(P_{UV}\), assume \(P_{U|V}(u,v)>0\) for all \((u,v)\) and set \(n=1\) for simplicity

  • Define the set \[ \calB_\gamma\eqdef\left\{(u,v)\in\calU\times\calV:\log\frac{1}{P_{U|V}(u|v)}\leq\gamma\right\}. \]

  • Encoding function \(f:\calU\to \set{1;M}\) created by assigning an index uniformly at random in \(\set{1;M}\) to each \(u\in\calU\)

  • Decoding function \(g:\intseq{1}{M}\times\calV:(m,v)\mapsto u^*\), where \(u^*=u\) if \(u\) is the unique sequence such that \((u,v)\in\calB_\gamma\) and \(f(u)=w\); otherwise, a random \(u\) is declared

On average (over the random binning to create \(F\)), \[ \E[C]{P_e} \leq \P[P_{U}]{U\notin \calB_\gamma} + \frac{2^{\min(\gamma,\log_2\abs{\calU})}}{M}. \]